Given the root of a binary tree, find the maximum average value of any subtree of that tree.
(A subtree of a tree is any node of that tree plus all its descendants. The average value of a tree is the sum of its values, divided by the number of nodes.)
Example 1:
Input: [5,6,1] Output: 6.00000 Explanation: For the node with value = 5 we have an average of (5 + 6 + 1) / 3 = 4. For the node with value = 6 we have an average of 6 / 1 = 6. For the node with value = 1 we have an average of 1 / 1 = 1. So the answer is 6 which is the maximum.
Note:
- The number of nodes in the tree is between
1and5000. - Each node will have a value between
0and100000. - Answers will be accepted as correct if they are within
10^-5of the correct answer.
Average Rating: 4.67 (12 votes)
Solution
Approach 1: Postorder Traversal
Intuition and Algorithm
To calculate average value of a subtree rooted at node, we need two things:
- Sum of all values of the nodes in the subtree of
node, let's refer to it asValueSum(node). - Count of the nodes in the
nodesubtree, let's refer to it asNodeCount(node).
Then, the average for subtree rooted at node will be ValueSum(node)/NodeCount(node).
Now, to calculate these values for a subtree rooted at node, we can derive them from the child nodes of node.
ValueSum(node) = ValueSum(node.left) + ValueSum(node.right) + Value(node)NodeCount(node) = NodeCount(node.left) + NodeCount(node.right) + 1
Also, for any leaf node leaf, we know that:
ValueSum(leaf) = node.valNodeCount(leaf) = 1
Looking at these equations, we can see that we can calculate average for each of the node in the tree by traversing bottom up i.e. first visit and calculate ValueSum and NodeCount for child nodes and then use these child nodes values to solve for parent node. This order of tree traversal is popularly known as postorder traversal.
You can read more about different binary tree traversals here.
Complexity Analysis
-
Time complexity : O(N), where N is the number of nodes in the tree. This is because we visit each and every node only once, as we do in postorder traversal.
-
Space complexity : O(N), because we will create N states for each of the nodes in the tree. Also, in cases where we have a skewed tree, we will implicitly maintain a recursion stack of size N, hence space complexity from this will also be O(N).
Simple DFS solution and understandable code -
Time complexity : O(n)
Space complexity: O(n)
class Solution:
def maximumAverageSubtree(self, root: TreeNode) -> float:
if not root:
return 0
def dfs(node=root):
# if node is None, return 0 as sum and 0 as no. of nodes
if node is None:
return (0, 0)
# go to left subtree and get total sum on that subtree, and the total nodes
sum_left, node_cnt_left = dfs(node.left)
# go to right subtree and get total sum on that subtree, and the total nodes
sum_right, node_cnt_right = dfs(node.right)
# calculate the total sum
_total_sum = node.val + sum_left + sum_right
# calculate the total no. of nodes
_total_nodes = 1 + node_cnt_left + node_cnt_right
# compute the avg
_avg = _total_sum / _total_nodes
# update max_avg if it is smaller than computed avg
if _avg > self.max_avg:
self.max_avg = _avg
# return the total sum and total nodes to previous stack call.
return (_total_sum, _total_nodes)
# set a variable to track max_avg
self.max_avg = float("-inf")
dfs()
return self.max_avg
Should the space complexity be O(logN) on average, O(N) for the worst case?
I think we only need to think of the stack frame.
The space for states is O(1) since it is not kept in memory all time. As soon as the current level of recursion returns, the state from subtrees is deleted in memory.
// we can keep the max average at class level
class Solution {
class State {
int sum;
int nodeCount;
public State(int sum, int nodeCount) {
this.sum = sum;
this.nodeCount = nodeCount;
}
}
double max = Double.MIN_VALUE;
public double maximumAverageSubtree(TreeNode root) {
maxAverage(root);
return max;
}
private State maxAverage(TreeNode root) {
if (root == null) return new State(0,0);
State left = maxAverage(root.left);
State right = maxAverage(root.right);
int nodeCount = left.nodeCount + right.nodeCount + 1;
int sum = left.sum + right.sum + root.val;
double average = (1.0 * (sum)) / nodeCount;
max = Math.max(max, average);
return new State(sum, nodeCount);
}
}
May 8, 2021 5:01 PM
Space used by State is O(1), not O(N).
Once you return to current node after recursion, you can free up the memory used by state OR in java it is not being referenced anywhere else except by the reference in current method scope, so will be eligible for Garbage Collection.
in test case 25, [4,3,1,0,2] max ave of 4 is 2.66, how come expects it 2
would someone comment please.
def maximumAverageSubtree(self, root: TreeNode) -> float:
def dfs(node, ma):
if node is None:
return
te = [node.val]
if node.left:
te.append(node.left.val)
if node.right:
te.append(node.right.val)
self.ma = max(self.ma, sum(te)/len(te))
dfs(node.left, ma)
dfs(node.right, ma)
return
self.ma = 0
dfs(root, 0)
print(self.ma)
return self.maPython solution, as this one only has Java/C++ using classes and structs.
class Solution:
def maximumAverageSubtree(self, root: TreeNode) -> float:
max_avg = 0
def getMaxAvgValue(root: TreeNode) -> (float, int):
nonlocal max_avg
if root == None:
return 0,0
total_left, nodes_left = getMaxAvgValue(root.left)
total_right, nodes_right = getMaxAvgValue(root.right)
total_curr = root.val + total_left + total_right
nodes_curr = (nodes_left + nodes_right + 1)
avg = total_curr / nodes_curr
if avg > max_avg:
max_avg = avg
return total_curr, nodes_curr
getMaxAvgValue(root)
return max_avg
Runs faster than 96% at O(N) time. You could also do same as Java Impl and return the elements as class above, or make it return thruple instead of tuple with max_avg in thruple.
November 16, 2020 10:05 AM
A simple dfs
fun maximumAverageSubtree(root: TreeNode?): Double {
var ans = 0.0
if (root == null) {
return ans
}
fun dfs(node: TreeNode?): Pair<Int, Int> { // returns <sum, number of nodes>
if (node == null) {
return 0 to 0
}
if (node.left == null && node.right == null) {
return node.`val` to 1
}
val (lSum, lNodes) = dfs(node.left)
val (rSum, rNodes) = dfs(node.right)
val curSum = lSum + rSum + node.`val`
val curNodes = lNodes + rNodes + 1
if (lNodes != 0) { // if check for dividebyzero exception
ans = maxOf(ans, lSum / (lNodes * 1.0))
}
if (rNodes != 0) {
ans = maxOf(ans, rSum / (rNodes * 1.0))
}
if (curNodes != 0) {
ans = maxOf(ans, curSum / (curNodes * 1.0))
}
return curSum to curNodes
}
dfs(root)
return ans
}
You don't have any submissions yet.
xxxxxxxxxx/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public: double maximumAverageSubtree(TreeNode* root) { }};
